package Thread;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: homechen
 * Date: 2024-03-13
 * Time: 20:38
 */


class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList(ListNode head) {
        // write code here
        // 定义一个优先级队列 以 val 升序的模式
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        ListNode cur = head;
        while (cur != null) {
            ListNode node = cur;
            queue.offer(node);
            cur = cur.next;
        }
        ListNode phread = null; // 自定义的一个哨兵节点
        ListNode prev = phread;
        while (!queue.isEmpty()) {
            ListNode node = queue.peek();
            prev.next = node;
            prev = node;
        }
        return phread.next;
    }
}
